package jiggle.app;
import jiggle.Edge;
import jiggle.Graph;
import jiggle.Vertex;

public class GraphFactory {
    
    public static Graph createPath(int n, int d) {
        Graph g = new Graph(d);

		Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		for (int i = 1; i < n; i++) g.insertEdge (V [i-1], V [i]);

		return g;
    }

    public static Graph createCycle(int n, int d) {
        Graph g = new Graph(d);

		Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		for (int i = 1; i < n; i++) g.insertEdge (V [i-1], V [i]);
		g.insertEdge (V [0], V [n - 1]);

		return g;
    }

    public static Graph createCompleteBinaryTree(int h, int d) {
        Graph g = new Graph(d);

		int twoToTheHMinusOne = (int) Math.pow (2, h) - 1;
		Vertex V [] = new Vertex [twoToTheHMinusOne];
		for (int i = 0; i < twoToTheHMinusOne; i++)
			V [i] = g.insertVertex ();
		for (int i = 1; i < twoToTheHMinusOne; i++)
		    g.insertEdge (V [(i-1)/2], V [i]);

		return g;
    }

	private static int randomInt (int n) {return (int) (Math.random () * n);}

	public static Graph createRandomConnectedGraph(int n, int m, int d) {
        Graph g = new Graph(d);

        Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		for (int i = 1; i < n; i++)
		    g.insertEdge (V [randomInt (i - 1)], V [i]);
		for (int i = 0; i < m - (n - 1); i++) {
			outerLoop: while (true) {
				int from = randomInt (n-1);
				int to = randomInt (n-1);
				if (from >= to) continue;
				for (int j = 0; j < n - 1 + i; j++) {
					Edge e = g.edges.get(j);					
					if ((V [from] == e.getFrom ()) &&
					    (V [to] == e.getTo ()))
						continue outerLoop;
				}
				g.insertEdge (V [from], V [to]);
				break;
			}
		}

		return g;
    }

    public static Graph createCycleOfCliques(int numberOfCliques, int sizeOfClique, int d) {
        Graph g = new Graph(d);

		int n = numberOfCliques * sizeOfClique;
		Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		for (int i = 0; i < numberOfCliques ; i++) {
			int cur = i * sizeOfClique;
			if (i < numberOfCliques - 1)
			    g.insertEdge (V [cur], V [cur + sizeOfClique]);
			else g.insertEdge (V [cur], V [0]);
			for (int j = cur + 1; j < cur + sizeOfClique; j++) {
				for (int k = cur; k < j; k++) {
				    g.insertEdge (V [k], V [j]);
				}
			}
		}

		return g;
    }

    public static Graph createTriangularMesh(int h, int d) {
        Graph g = new Graph(d);

		int n = (h * (h + 1)) / 2;
		Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		int cur = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j <= i; j++) {
				if (j < i) g.insertEdge (V [cur], V [cur + 1]);
				if (i < h - 1) {
				    g.insertEdge (V [cur], V [cur + i + 1]);
				    g.insertEdge (V [cur], V [cur + i + 2]);
				}
				++cur;
			}
		}

		return g;
    }

    public static Graph createSquareMesh(int n, int d) {
        Graph g = new Graph(d);

		Vertex grid [] [] = new Vertex [n] [n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				grid [i] [j] = g.insertVertex ();
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
			    g.insertEdge (grid [i] [j], grid [i] [j+1]);
			    g.insertEdge (grid [j] [i], grid [j+1] [i]);
			}
		}

		return g;
    }

    public static Graph createTorus(int n, int d) {
        Graph g = new Graph(d);

		Vertex grid [] [] = new Vertex [n] [n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				grid [i] [j] = g.insertVertex ();
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
			    g.insertEdge (grid [i] [j], grid [i] [j+1]);
				g.insertEdge (grid [j] [i], grid [j+1] [i]);
			}
			g.insertEdge (grid [0] [i], grid [n-1] [i]);
			g.insertEdge (grid [i] [0], grid [i] [n-1]);
		}

		return g;
    }

    public static Graph createHypercube(int n, int d) {
        Graph g = new Graph(d);

		int twoToTheN = (int) Math.pow (2, n);
		Vertex V [] = new Vertex [twoToTheN];
		for (int i = 0; i < twoToTheN; i++)	{
			V [i] = g.insertVertex ();
			//int j = i;
		}
		for (int i = 0; i < twoToTheN; i++) {
			for (int j = 1; j < twoToTheN; j*=2) {
				if ((i & j) == 0)
				    g.insertEdge (V [i], V [i+j]);
			}
		}
        
		return g;
    }

    public static Graph createCompleteBipartiteGraph(int n, int d) {
        Graph g = new Graph(d);

		Vertex V [] = new Vertex [2 * n];
		for (int i = 0; i < 2 * n; i++) V [i] = g.insertVertex ();
		for (int i = 0; i < n; i++)
			for (int j = n; j < 2 * n; j++) g.insertEdge (V [i], V [j]);
        
		return g;
    }

    public static Graph createCompleteGraph(int n, int d) {
        Graph g = new Graph(d);

		Vertex V [] = new Vertex [n];
		for (int i = 0; i < n; i++) V [i] = g.insertVertex ();
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
			    g.insertEdge (V [i], V [j]);
			}
		}
        
		return g;
    }

    
}
